The Twofish Encryption Algorithm: A 128-Bit Block Cipher The Twofish Encryption Algorithm: A 128-Bit Block Cipher
by Bruce Schneier ; John Kelsey ; Doug Whiting ; David Wagner ; Chris Hall ; Niels Ferguson
Wiley Computer Publishing, John Wiley & Sons, Inc.
ISBN: 0471353817   Pub Date: 03/01/99
  

Previous Table of Contents Next


10.8 Family Key Variant: Twofish-FK

We often see systems that use a proprietary variant of an existing cipher, altered in some hopefully security-neutral way to prevent that system from interoperating with standard implementations of the cipher. A family key is a way of designing this into the algorithm: each different family key is used to define a different variant of the cipher. In some sense, the family key is like an additional key to the cipher, but in general, it is acceptable for the family key to be very computationally expensive to change. We would expect nearly all Twofish implementations that used any family key to use only one family key.

Our goals for the family key algorithm are as follows:

  No family key variant should be substantially weaker than the original cipher.
  Related-key attacks between different unknown but related family keys, or between a known family key and the original cipher, should be hard to mount.
  The family key should not merely reorder the set of 128-by-128-bit permutations provided by the cipher, it should change that set.

A Twofish family key is simply a 256-bit random Twofish key. This key, FK, is used to derive several blocks of bits, as follows:

1.  Preprocessing Step:
This step is done once per family key.
a)  T0 = FK.
b)  T1 = (EFK(0), EFK(1)) ⊕ FK.
c)  T2 = EFK(2).
d)  T3 = EFK(3).
e)  T4 = First 8 bytes of EFK(4).

Note that, using our little-endian convention, the small integers used as plaintext inputs should occur in the first plaintext byte.
2.  Key Scheduling Step: This step is done once per key used under this family key.
a)  Before subkey generation, T0 is XORed into the key, using as many of the leading bytes of T0 as necessary.
b)  After subkey generation, T2 is XORed into the pre-whitening subkeys, T3 is XORed into the post-whitening subkeys, and T4 is XORed into each round’s 64-bit subkey block.
c)  Before the cipher’s S-boxes are derived, T1, is XORed into the key. Once again, we use as many of the leading bytes of T1, as we need. Each byte of the key is then passed through the byte permutation q0, and the result is passed through the RS matrix to get S. Note that the definition of T1, means that the effect of the first XOR of FK into the key is undone.

Note the properties of the alterations made by any family key:

  The keyspace is simply permuted for the initial subkey generation.
  The subkeys are altered in a simple way. However, there is strong evidence that this alteration cannot occur by changing keys, based on the same difference sequence analysis used in discussing related-key attacks on Twofish.
  The S-boxes used in the cipher are altered in a powerful way, but one which does not alter the basic required properties of the key schedule. Getting no changes in the S-boxes used in the cipher still requires changing at least five bytes of key, and those five bytes of key must change five of the S-boxes used for subkey generation.

10.8.1 Analysis

Effects of Family Keys on Cryptanalysis. We are not aware of any substantial difference in the difficulty of cryptanalyzing the family key version of the cipher rather than the regular version. The cipher’s operations are unchanged by the family key; only subkey and S-box generation are changed. However, they are changed in simple ways; the S-boxes are generated in exactly the same way as before, but the key material provided to them is processed in a simple way first; the round subkeys are generated in the same way as before (again, with the key material processed in a simple way first), and then have a constant 64-bit value XORed in. Related-key attacks of the kind we have been able to consider are made slightly harder, rather than easier, by this 64-bit value. The new constants XORed into the whitening subkeys simply permute the input and output space of the cipher in a very simple way.

Related Keys across Family Keys. Related-key attacks under the same family key appear, as we said above, to be at least as hard as related-key attacks in normal Twofish. There is still the question, however, of whether there are interesting related keys across different family keys. It is hard to see how such related keys would be used, but the analysis may be worth pursuing anyway.

An interesting question, from the perspective of an attacker, is whether there ar e pairs of keys that give identical subkeys except for the constant values XORed into them, and that also give identical S-boxes. By allowing an attacker to put a constant XOR into all round subkeys, such pairs of keys would provide a useful avenue of attack.

This can be done by finding a pair of related family keys, FK, FK*, that are identical in their first 128 bits, and a pair of 128-bit cipher keys, M, M*, such that M generates the same set of S-boxes with FK that M* does with FK*. For a random pair of M, M* values, this has probability 2-64 of happening, Thus, an attacker given complete control over M, M* and knowledge of FK, FK* can find such a pair of keys and family keys. However, this does not seem to translate into any kind of clean related-key attack; the attacker must actually choose the specific keys used.

We do not consider this to be a valid attack against the system. In general, related-key attacks between family keys seem unrealistic, but one which also requires the attacker to be able to choose specific key values he is trying to recover is also pointless.

A Valid Related-key Attack. An attacker can also try to find quadruples FK, FK*, M, M* such that the subkey generation and the S-box generation both get identical values. This requires that

T0M = T0*M*

T1M = T1*M*

If FK, FK* have the property that

T0T0* = T1T1* = δ

then related-key pairs M, M ⊕ Ϙ will put a fixed XOR difference into every round subkey, and may allow some kind of related-key attack. Again, we do not think this is an interesting attack; the attacker must force the family keys to be chosen this way, since the probability that any given pair of family keys will work this way is (for 128-bit cipher keys) 2-128. We do not expect such relationships to occur by chance until about 264 family keys are in use.


Previous Table of Contents Next